/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
    RC retVal;
    retVal = pf.open(indexname, mode);
    if (retVal != 0)
        return retVal;
        // Do initialization if this index was just created
    if (pf.endPid() == 0) {
        char buffer[PageFile::PAGE_SIZE];
        int* heightInit = (int*) &buffer[HEIGHT_INDEX];
        PageId* rootInit = (int*) &buffer[ROOT_INDEX];
        *heightInit = 0;
        *rootInit = -1;
        retVal = pf.write(0, buffer);
    }
    else {
        char buffer[PageFile::PAGE_SIZE];
        pf.read(0, buffer);
        rootPid = buffer[ROOT_INDEX];
        treeHeight = buffer[HEIGHT_INDEX];
    }
    return retVal;
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
    return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
    if (treeHeight == 0) {
        BTLeafNode rootNode;
        rootNode.insert(key, rid);
        rootNode.setNextNodePtr(-1);
        treeHeight++;
    }
    else {
        bool nodeOverflow;
        int overflowKey;
        int siblingPid;
        insertHelper(key, rid, rootPid, 1, nodeOverflow, overflowKey, siblingPid);
        
            // New root node
        if (nodeOverflow) {
            BTNonLeafNode newRootNode;
            newRootNode.initializeRoot(rootPid, overflowKey, siblingPid);
            rootPid = pf.endPid();
            newRootNode.write(pf.endPid(), pf);
            treeHeight++;
        }
    }
    return 0;
}

RC BTreeIndex::insertHelper(int key, const RecordId& rid, PageId currentNodePid, int currentHeight, bool& nodeOverflow, int& overflowKey, int& siblingNodePid) 
{
    
        // Base case, leaf level
    if (currentHeight == treeHeight) {
        BTLeafNode leafNode;
        leafNode.read(currentNodePid, pf);
        
            // Insert, and check if leaf overflow
        if (leafNode.insert(key, rid) == RC_NODE_FULL) {
            BTLeafNode siblingLeaf;
            int siblingKey;
            leafNode.insertAndSplit(key, rid, siblingLeaf, siblingKey);
            siblingLeaf.write(pf.endPid(), pf);
            leafNode.setNextNodePtr(pf.endPid() - 1);
            nodeOverflow = true;
            overflowKey = siblingKey;
            siblingNodePid = pf.endPid() - 1;
        }
    }
        // Recursive case
    else {
        BTNonLeafNode currentNode;
        currentNode.read(currentNodePid, pf);
        PageId pidToFollow;
        currentNode.locateChildPtr(key, pidToFollow);
        
        PageId secondChildPid;
        bool nOverflow = false;
        int ovfKey;
        insertHelper(key, rid, pidToFollow, currentHeight + 1, nOverflow, ovfKey, secondChildPid);
        if (nOverflow) {
                // Check if nonleaf overflow
            if (currentNode.insert(ovfKey, secondChildPid) == RC_NODE_FULL) {
                BTNonLeafNode siblingNode;
                currentNode.insertAndSplit(ovfKey, secondChildPid, siblingNode, overflowKey);
                siblingNodePid = pf.endPid();
                siblingNode.write(pf.endPid(), pf);
                nodeOverflow = true;
            }
        }     
    }    
    return 0;
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
    int currentHeight = 1;
    if (treeHeight == 0) {
        return RC_NO_SUCH_RECORD;
    }
    else if (treeHeight == 1) {
        BTLeafNode rootNode;
        rootNode.read(rootPid, pf);
        int eid;
        if (rootNode.locate(searchKey, eid) == RC_NO_SUCH_RECORD)
            cursor.pid = -1;
        cursor.pid = rootPid;
        cursor.eid = eid;
        return 0;
    }
    else {
        BTNonLeafNode currentNode;
        currentNode.read(rootPid, pf);
        PageId childPid;
        currentNode.locateChildPtr(searchKey, childPid);
        currentHeight++;
        while(currentHeight < treeHeight) {
            currentNode.read(childPid, pf);
            currentNode.locateChildPtr(searchKey, childPid);
            currentHeight++;
        }
        int eid;
        BTLeafNode leafNode;
        leafNode.read(childPid, pf);
        if (leafNode.locate(searchKey, eid) == RC_NO_SUCH_RECORD) {
            cursor.pid = leafNode.getNextNodePtr();
            cursor.eid = 0;
            return 0;
        }
        cursor.pid = childPid;
        cursor.eid = eid;
    }
    return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to an leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
    BTLeafNode leafNode;
    if (cursor.pid == -1)
       return RC_INVALID_PID;
    leafNode.read(cursor.pid, pf);
    leafNode.readEntry(cursor.eid, key, rid);
    if (leafNode.getKeyCount() == cursor.eid + 1) {
        cursor.pid = leafNode.getNextNodePtr();
        cursor.eid = 0;
    }
    else {
        cursor.eid++;
    }
    return 0;
}
